package com.huawei.M01.iterator;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RangeFreqQuery {
    private int[] rangeArr;

    // 用于存放数字对应的下标集合
    private Map<Integer, List<Integer>> helpMap;

    public RangeFreqQuery(int[] arr) {
        rangeArr = new int[arr.length];
        helpMap = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            rangeArr[i] = arr[i];
            helpMap.putIfAbsent(arr[i], new ArrayList<>());
            helpMap.get(arr[i]).add(i); // 讲下标添加到map中
        }
    }

    public int query(int left, int right, int value) {
        if (!helpMap.containsKey(value)) {
            return 0;
        }
        List<Integer> resultList = helpMap.get(value);
        // 通过二分法查找做端点
        int mid;
        int l = 0;
        int r = resultList.size();
        while (l < r) {
            mid = l + (r - l) / 2;
            if (resultList.get(mid) >= left) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int ld = l;
        l = 0;
        r = resultList.size();
        while (l < r) {
            mid = l + (r - l) / 2;
            if (resultList.get(mid) <= right) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        int rd = l;
        return rd - ld;
    }
}
